package Array;

/**
 * 134. 加油站
 *
 * 在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
 * 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
 * 给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
 *
 * 思路：使用贪心的思想， 因为是一个环形，所以我们可以首先定义这么一个结论
 *  如果总油量大于总花费，则一定存在一个解，然后我们再去思考以哪个节点作为起点
 *  这里使用贪心，即比较每一步的油耗，如果油耗差小于0，则当前start必不可能是起点，这时将start切换为下一个，油耗差重新计算
 *  油耗差计算公式： tank += gas[i]-cost[i]
 */
public class L_134 {

    public int canCompleteCircuit(int[] gas, int[] cost) {

        int totalGas =0,totalCost=0,start=0,tank=0;
        for (int i = 0; i < gas.length; i++) {
            totalGas += gas[i];
            totalCost += cost[i];
            tank += gas[i]-cost[i];
            // 如果油耗差小于0,则以当前起点，汽车必不可能到达，将起点设置为下一个
            if(tank <0 ){
                start = i + 1;
                // 油耗差重新清0
                tank = 0;
            }
        }
        // 如果总油量大于等于总花费，则一定存在解
        return totalGas >= totalCost ? start : -1;
    }
}
